Trong lúc sống lưu vong, Thoát Lý đã nhận được hỗ trợ từ Thiết Mộc Chân- sau đó đã tiến hành cuộc chinh phạt bộ tộc Miệt Nhi Khất lần hai và trao một phần lớn những chiến lợi phẩm cho Thoát Lý. Vị Vương Hãn đã phân phát những tặng phẩm này cho các thủ lĩnh tộc Khắc Liệt để củng cố liên minh với bộ tộc gốc gác của mình. Thiết Mộc Chân sau đó đã tấn công một chi tộc Khắc Liệt là Tumen Tubegen và một phần lớn trong số những người sống sót đã quy phục Thoát Lý. Thoát Lý đã hoàn toàn giành lại quyền kiểm soát tộc Khắc Liệt vào khoảng năm 1198. Người Nãi Man vẫn giữ vị trí trung lập mà không tiến hành chi viện cho Erke Qara vì bộ tộc Nãi Man đã bị chia rẻ nội bộ giữa hai vị hãn là Khan Buyruq chiếm phần phía nam và Tayang khan thừa kế phần phía bắc của vùng đất Naiman. Sau khi thất bại, Erke Qara đã bỏ trốn một lần nữa sang lãnh thổ của Buyruq khan. Để ban thưởng cho những chiến binh Khắc Liệt vẫn trung thành với mình, Thoát Lý đã ra lệnh cho họ cướp bóc bộ tộc Miệt Nhi Khất đã bị suy yếu lần thứ ba. Những thủ lĩnh quan trọng của tộc Miệt Nhi Khất bao gồm hai con trai của Toqto'a-beki đã bị bắt trong khi một người khác bị sát hại. Anh trai của Thoát Lý là Jakha Gambhu đã trở thành anh em kết nghĩa của Thiết Mộc Chân.

Mối quan hệ với người Nãi Man

Vào khoảng năm 1199, Thoát Lý muốn giải quyết triệt để mâu thuẫn với người Nãi Man và sự đấu đá nội bộ giữa hai anh em là hai vị hãn của bộ tộc này là một cơ hội tốt để tấn công. Nếu quân Thoát Lý tấn công một trong hai vị hãn, gần như chắc chắn rằng người kia sẽ không can dự và Thoát Lý có thể lần lượt tiêu diệt từng kẻ thù mà không cần phải đối đầu với hai đối thủ cùng lúc, vốn đã có thể hình thành một liên minh đáng gờm. Thoát Lý đã thành công trong việc chiêu mộ Thiết Mộc Chân và Trát Mộc Hợp là thủ lĩnh bộ tộc Trát Đạt Lan thành đồng minh một lần nữa, vì gần đây họ đã trở thành kẻ thù. Thiết Mộc Chân và Trát Mộc Hợp đã chấp thuận nhưng không thực sự tin tưởng nhau. Khi các lực lượng của liên minh tập hợp lại để chống lại quân đội Nãi Man của Buyruq, họ nhận ra rằng vùng đất Nãi Man có lợi cho một cuộc truy đuổi lâu dài. Thật vậy, Thoát Lý đã gặp rất nhiều khó khăn để truy đuổi kẻ thù của mình vì họ có nhiều đất để tiến hành trốn thoát. Sau chuyến truy đuổi vài trăm kilomet, Thoát Ký nhận ra rằng mình không bao giờ có thể tóm được kẻ thù và quay về. Tướng Kökse Sabraq của Buyruq đã tấn công Thoát Lý khi ông tách biệt khỏi Thiết Mộc Chân, đánh bại con trai của Thoát Lý là Senggüm, bắt giữ con trai và vợ của ông ta. Tuy nhiên họ đã bị đánh trả nhờ sự chi viện từ Thiết Mộc Chân.

Năm 1200, Thoát Lý tiến hành chi viện khi Thiết Mộc Chân bị tấn công bởi một liên minh do tộc Thái Xích Ô thành lập, do kẻ thù cũ của Thiết Mộc Chân là Targhutai Kiriltuk chỉ huy và quân Miệt Nhi Khất do Toqto'a Beki vốn đã phục vị cho con trai mình trên bờ sông Onon.

Mối quan hệ với Trát Mộc Hợp

Năm 1201, Trát Mộc Hợp đang có quan hệ thù địch với Thiết Mộc Chân. Một loạt các bộ tộc Mông Cổ bao gồm Thái Xích Ô, Ikires, Qorolas, Salji'ut, Đỗ Nhĩ Bách Đặc, Suldus, Qatagin, Besud, Miệt Nhi Khất, Ngõa Lạc và cả người Tatars đã công nhận Trát Mộc Hợp là "Cổ Nhi hãn". Thoát Lý đã quyết định liên minh với Thiết Mộc Chân để chống lại thế lực ngày càng tăng của Trác Mộc Hợp. Thoát Lý, Jakha Gambu và Thiết Mộc Chân đã đi vào thung lũng Kerulen với 15000 quân. Khi trông thấy kẻ thù, đoàn quân leo lên núi vì để đi tắt đón đầu kẻ thù. Đó cũng là lúc Buyruq của người Nãi Man đã gia nhập Trát Mộc Hợp. Thoát Lý và Thiết Mộc Chân đã chiến đấu một trận phòng thủ rất khó khăn và nguy hiểm. Mưa xối xả khiến những ngọn đồi núi trập trùng, binh sĩ rơi từ đỉnh cao xuống những khe núi. Sau khi kẻ thù rút hết lực lượng, Thoát Lý rời đi để trở về sông Tula cùng với binh sĩ của mình. Thiết Mộc Chân đã truy đuổi kẻ thù và kết liễu nhiều kẻ còn đang trên lưng ngựa. Targhutai được cho là đã bị thương đến chết từ trận chiến.

Trát Mộc Hợp đã thất bại nặng nề trong trận đánh đầu tiên và Buyruq đã giành quyền chỉ huy quân đội vào năm 1202. Thiết Mộc Chân đã chủ động thực hiện một cuộc đồ sát người Tatar khiến số lượng dân Tatars giảm đi đáng kể. Khi Thiết Mộc Chân và Thoát Lý quay trở lại vùng núi, nhưng lần này là ở phần phía nam của họ phải đối mặt với đội quân do Kuchuguden chỉ huy, trong số đó có tộc Miệt Nhi Khất, Nam Nãi Man, Ngõa Lạc và các bộ tộc theo Trát Mộc Hợp. Sáu bộ tộc đã rời khỏi liên minh với Trát Mộc Hợp và hiện chỉ còn bốn. Một lần nữa, các con dốc, cây cối và các chướng ngại vật tự nhiên khác đã làm chậm bước tiến của rất nhiều kẻ thù của Thoát Lý và Thiết Mộc Chân Khiến cuộc chiến dần trở nên thuận lợi.